// https://www.lintcode.com/problem/maximal-square/description

class Solution {
public:
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    int maxSquare(vector<vector<int>> &matrix) {
        if (matrix.empty() || matrix[0].empty())
        {
            return 0;
        }
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> res(n, vector<int>(m));
        int maxVal = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (i == 0 || j == 0)
                    res[i][j] = matrix[i][j]; //不要continue,1的也要拿来比较的
                else if (matrix[i][j] == 0)
                    res[i][j] = 0;
                else
                    res[i][j] = min(res[i - 1][j - 1], min(res[i - 1][j], res[i][j - 1])) + 1;
                if (res[i][j] > maxVal)
                    maxVal = res[i][j];
            }
        }
        return maxVal * maxVal;
    }
};